package com.example.test.算法;

import java.util.Arrays;

public class 希尔排序 {


    /**
     * @Description 希尔排序 从小到大
     * 初始 4, 5, 6, 3, 2, 1, 9, 8, 10
     * 步长 = n/2,每次都步长结束,都除以2 ,直到1为止
     * 初始长度为 9 第一次步长为 4,那么分组即: 4-2,5-1,6-9,3-8,2-10,
     * 比较之后交换:交换后的顺序为 2, 1, 6, 3, 4, 5, 9, 8, 10
     * 第二次步长为 2 那么分组即: 2-6,1-3,6-4,3-5,4-9,5-8,9-10
     * 比较之后交换:交换后的顺序为 2, 1, 4, 3, 6, 5, 9, 8, 10
     * ......................
     * @Author 寂寞旅行
     * @Date 10:26 2022/2/26
     * @Param [args]
     **/
    public static void main(String[] args) {
        int[] arr = {4, 5, 6, 3, 2, 1, 9, 8, 10};

        int buchang = arr.length / 2;

        int index = 0;
        while (buchang >= 1) {
            index++;
            for (int i = 0; i < arr.length; i++) {
                int temp;
                for (int j = buchang + i; j < arr.length; j += buchang) {
                    if (arr[i] > arr[j]) {
                        temp = arr[i];
                        arr[i] = arr[j];
                        arr[j] = temp;
                    }
                }
            }
            buchang = buchang / 2;
            System.out.println("第" + index + "次" + Arrays.toString(arr));
        }

    }
}
